#pragma once
#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

typedef int SLDateType;//使  int 为顺序表存储数据类型
typedef struct SeqList{
    SLDateType *a;//动态存储数据的数组
    int size;//顺序表数据多少
    int capacity;//顺序表容量大小
}SeqList;


void SeqListInit(SeqList* ps);//初始化一个顺序表
void SeqListDestroy(SeqList* ps);//销毁一个顺序表

void SeqListPrint(SeqList* ps);//打印表元素

void SeqListCheck(SeqList*ps);//检查顺序表是否为满,满就扩容
void SeqListPushBack(SeqList* ps, SLDateType x);//数据尾插
void SeqListPushFront(SeqList* ps, SLDateType x);//数据头插
void SeqListPopFront(SeqList* ps);//头删
void SeqListPopBack(SeqList* ps);//尾删

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

void SeqListInit(SeqList* ps)
{
    assert(ps);//防止指针为空
    ps->a=(SLDateType*) malloc(sizeof (SLDateType)*4);//为顺序表申请存放数据的空间
    ps->size=0;
    ps->capacity=4;
}

void SeqListDestroy(SeqList* ps)
{
    free(ps->a);//销毁数组
    ps->a=NULL;//防止a成为野指针
    ps->capacity=0;
    ps->size=0;
}

void SeqListPrint(SeqList* ps)
{
    for (int i = 0; i < ps->size; ++i)
    {
        printf("%d ",ps->a[i]);
    }
    printf("\n");
}

void SeqListCheck(SeqList*ps)
{
    if(ps->size==ps->capacity)
    {
        SLDateType *tmp=(SLDateType*) realloc(ps->a,sizeof (SLDateType)*ps->capacity*2);
        if(tmp==NULL)//申请失败
        {
            perror("realloc error\n");
            return;
        }
        ps->a=tmp;//将扩容过的空间给顺序表
        ps->capacity*=2;//更新顺序表容量
    }
}

void SeqListPushBack(SeqList* ps, SLDateType x)
{
    SeqListCheck(ps);//先检查是否为满，如果满就扩容
    ps->a[ps->size++]=x;//尾插数据
}

void SeqListPushFront(SeqList* ps, SLDateType x)
{
    SeqListCheck(ps);
    //从最后一位开始挪动
    int end=ps->size-1;//end是顺序表最后一个有效数据的索引
    //end从后往前遍历数组，并把索引为end的数据赋给索引为end+1的数据达到向后挪动的效果
    while (end >= 0)
    {
        ps->a[end+1]=ps->a[end];
        end--;
    }
    ps->a[0]=x;
    ps->size++;
}

void SeqListPopBack(SeqList* ps)
{
    //解决顺序表为空的情况
    //if(ps->size==0)return;//Normal Check
    assert(ps->size>0);//Force Check
    //不关心最后一位的数据是多少
    ps->size--;
}
void SeqListPopFront(SeqList* ps)
{
    assert(ps->size>0);//解决为空的情况
    //从后往前挪动，把第一个元素覆盖
    int start=0;//start遍历顺序表
    while (start<ps->size-1)
    {
        ps->a[start]=ps->a[start+1];
        start++;
    }
    ps->size--;
}

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
    assert(0<=pos&&pos<=ps->size);//防止越界
    SeqListCheck(ps);
    int end=ps->size-1;//end是最后一个有效数据的索引
    while (end>=pos)//pos之前的数据不动，后面的数据后移动
    {
        ps->a[end+1]=ps->a[end];
        --end;
    }
    ps->a[pos]=x;
    ps->size++;
}

void SeqListErase(SeqList* ps, int pos)
{
    assert(0<=pos&&pos<=ps->size);
    int start=pos;
    while (start<ps->size-1)//覆盖
    {
        ps->a[start]=ps->a[start+1];
        start++;
    }
    ps->size--;
}

int SeqListFind(SeqList* ps, SLDateType x)
{
    int index=0;
    for (;index <ps->size ; index++)
    {
        if(ps->a[index]==x)
            return index;
    }
    return -1;
}